package data_structure.mooc;

import data_structure.implement.Map;

/**
 * 红黑树：
 * @param <K>
 * @param <V>
 */
public class RABTree<K extends Comparable<K>,V>implements Map<K,V> {


    private static final boolean RED=true;
    private static final boolean BLACK=false;
    class Node{

        private K key;
        private V value;
        private Node left,right;
        //颜色
        private boolean color;
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            left=null;
            right=null;
            //初始时，默认颜色为红色
            this.color = RED;
        }
        public Node(){
            this(null,null);
        }

        @Override
        public String toString() {
           return key.toString ()+":"+value.toString ();
        }
    }
    private Node root;
    private int size;
    public RABTree(){
        root = null;
        size = 0;
    }

    /**
     * 返回当前节点的颜色
     * @param node
     * @return
     */
    private boolean isRed(Node node){
        if (node == null) {
            return BLACK;
        }
        return node.color;
    }

    /**
     *
     * 返回左旋转后的根节点(node.left)
     * @param node
     * @return
     */
    private Node leftRotate(Node node){
        Node newRoot=node.right;
        //更新node节点
        node.right=newRoot.left;
        //维护newRoot节点
        newRoot.left=node;
        //新的根节点的颜色和旧的相同
        newRoot.color=node.color;
        node.color=RED;
        return newRoot;
    }

    /***
     * 在向三节点添加元素时存在颜色反转
     * @param node
     */
    private void flipColors(Node node){
        node.color=RED;
        node.left.color=BLACK;
        node.right.color=BLACK;
    }

    /**
     * 右旋转
     * @param node
     * @return
     */
    private Node rightRotate(Node node){
        Node newRoot=node.left;
        node.left=newRoot.right;

        newRoot.right=node;
        newRoot.color = node.color;
        node.color=RED;

        return newRoot;
    }
    @Override
    public void add(K key, V value) {
        root=add (root,key,value);
        //保持根节点为黑色
        root.color=BLACK;
    }
    private Node add(Node node,K key,V value){
        if(node==null){
            node = new Node(key,value);
            size++;
        }
        if(node.key.compareTo (key)>0){
            node.left=add (node.left,key,value);
        }else if(node.key.compareTo(key) < 0){
            node.right = add(node.right, key, value);
        }else{
            node.value=value;
        }

        //左旋转
        if(isRed (node.right)&&!isRed (node.left)){
            node=leftRotate (node);
        }

        //右旋转
        if(isRed (node.left)&&isRed (node.left.left)){
            node=rightRotate(node);
        }

        //颜色反转
        if(isRed (node.left)&&isRed(node.right)){
            flipColors (node);
        }
        return node;
    }

    private Node minNode(Node node){
        Node curr=node;
        while(curr.left!=null){
            curr = curr.left;
        }
        return curr;
    }

    /**
     * 返回删除最小节点后的根节点
     * @param node
     * @return
     */
    private Node removeMin(Node node){

        if(node.left==null){
            Node rightNode=node.right;
            node.right=null;
            size--;
            return rightNode;
        }
        node.left = removeMin (node.left);
        return node;
    }

    private Node remove(Node node,K key){

        if(node==null){
            return null;
        }
        if(key.compareTo (node.key)<0){
            node.left=remove(node.left, key);
            return node;
        }else if (key.compareTo(node.key) > 0){
            node.right = remove(node.right, key);
            return node;
        }else{
            if(node.left==null){
                Node rightNode=node.right;
                node.right=null;
                size--;
                return rightNode;
            }
            if(node.right == null){
                Node leftNode=node.left;
                node.left=null;
                size--;
                return leftNode;
            }

            Node rightNode=removeMin(node.right);
//            size--;
            Node successor=minNode (node.right);
            successor.left=node.left;
            successor.right=rightNode;
            node.left=node.right=null;
            return successor;
        }

    }

    /**
     * 返回以node为根节点的key所在的节点
     * @param node
     * @param key
     * @return
     */
    private Node getNode(Node node,K key){

        if(node==null)return null;
        if(key.compareTo (node.key)<0){
            return getNode (node.left, key);
        }else if (key.compareTo(node.key) > 0) {
            return getNode(node.right, key);
        }
        return node;
    }
    @Override
    public V remove(K key) {

        Node del=getNode (root,key);
        if(del == null)return null;
        else{
            return remove (root,key).value;
        }
    }

    @Override
    public boolean contains(K key) {
        return getNode(root, key)!=null;
    }

    @Override
    public void set(K key, V newValue) {
        Node node = getNode(root, key);
        if(node==null){
            throw new IllegalArgumentException (key+"doesn't exit");
        }
        node.value = newValue;
    }

    @Override
    public V get(K key) {
        return getNode(root, key)==null?null:getNode(root, key).value;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    public void inOrder(){
        inOrder (root);
    }
    private void inOrder(Node node){
        if(node==null)return;
        inOrder (node.left);
        System.out.println(node.key+":"+node.value);
        inOrder(node.right);
    }

}
